package 困难.动态规划.背包.多维背包;

/**
 * 考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维
 * 整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的
 * 题目有 counti 道，每道题目对应 marksi 分。
 * 返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要
 * 对 109 +7 取余。
 * 注意，同类型题目无法区分。
 * 比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1
 * 和第 3 道题目或者第 2 和第 3 道题目是相同的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-ways-to-earn-points
 */
public class 获得分数的方法数_6310 {

    public static void main(String[] args) {

    }

    /**
     * 1，定义子问题
     * dp[i][j] 在 types 的前 i 个类型的题目中得到 j 分数
     * 的方法数
     * 2，多维背包由01背包变种而来，区别是某种类型的物品可以
     * 选择有限数量
     * 3，对于某个类型的题目，有 types[i][0] 种情况，可以完成
     * 1 或者 2 ...或者 types[i][0] 道题，每种情况的方法数是
     * 需要累加的
     */
    public int waysToReachTarget(int target, int[][] types) {
        long[][] dp = new long[types.length + 1][target + 1];
        dp[0][0] = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j <= target; j++) {
                int mark = types[i - 1][1];
                // 选某几道题
                for (int count = 1; count <= types[i - 1][0] &&
                        j - count * mark >= 0; count++) {
                    dp[i][j] += dp[i - 1][j - count * mark];
                }
                // 不选
                dp[i][j] += dp[i - 1][j];
                dp[i][j] %= 1000000007;
            }
        }

        return (int) dp[types.length][target];
    }

}
